package org.example.DataStructure.LinkList;

import java.util.Iterator;

//单向链表的实现
public class LinkList<T> implements Iterable<T> {
    //节点内部类
    private static class Node<T> {
        //数据域
        T data;
        //指针域
        Node<T> next;

        //构造方法
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    //成员变量
    //记录头节点
    private final Node<T> head;
    //记录链表的长度
    private int N;

    //构造方法
    public LinkList() {
        //初始化头节点
        this.head = new Node<T>(null, null);
        //初始化元素个数
        this.N = 0;
    }

    //清空链表
    public void clear() {
        //将头节点的next指针设为null
        this.head.next = null;
        //将元素个数设为0
        this.N = 0;
    }

    //判断线性表是否为空，是返回true不是返回false
    public boolean isEmpty() {
        return this.N == 0;
    }

    //获取链表中元素的个数
    public int length() {
        return this.N;
    }

    //获取并返回链表中第i个元素的值
    public T get(int i) {
        //边界检查
        if (i < 0 || i >= this.N) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + this.N);
        }
        //通过循环从头节点往后找
        Node<T> node = this.head.next;
        for (int index = 0; index < i; index++) {
            node = node.next;
        }
        return (T) node.data;
    }

    //向单向链表末尾添加一个元素
    public void insert(T t) {
        //找到最后的节点
        Node<T> current = this.head;
        while (current.next != null) {
            current = current.next;
        }
        //创建新节点保存元素T
        //让当前节点指向新节点
        current.next = new Node<T>(t, null);
        //元素的个数+1
        this.N++;
    }

    //向单向链表的指定位置添加一个元素
    public void insert(int i, T t) {
        //边界检查
        if (i < 0 || i >= this.N) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + this.N);
        }
        //找到第i-1个节点
        Node<T> pre = this.head;
        for (int index = 0; index < i - 1; index++) {
            pre = pre.next;
        }
        //创建新元素并更改后继指针
        //插入元素
        pre.next = new Node<T>(t, pre.next);
        //元素数量+1
        this.N++;
    }

    //删除并返回指定元素
    public T remove(int i) {
        //边界检查
        if (i < 0 || i >= this.N) {
            throw new IndexOutOfBoundsException("Index: " + i + ", Size: " + this.N);
        }
        //找到第i-1个节点
        Node<T> pre = this.head;
        for (int index = 0; index < i; index++) {
            pre = pre.next;
        }
        //找到i位置的节点
        Node<T> current = pre.next;
        //让前一个节点指向下一个节点
        pre.next = current.next;
        //元素个数-1
        this.N--;
        //返回删除的节点数据
        return current.data;
    }

    //返回线性表中首次出现的指定数据元素的序号，若不存在返回-1
    public int indexOf(T t) {
        //判断链表非空
        if (this.isEmpty()) {
            return -1;
        }
        //从头节点开始一次找到每一个节点的date和t比较,相同直接返回
        Node<T> current = this.head.next;
        for (int index = 0; current != null; index++) {
            if (current.data.equals(t)) {
                return index;
            }
            current = current.next;
        }
        return -1;
    }

    //实现遍历方法
    @Override
    public Iterator<T> iterator() {
        //利用匿名内部类的方法提供类
        return new Iterator<T>() {
            private Node<T> current = head;

            @Override
            public boolean hasNext() {
                return current.next != null;
            }

            @Override
            public T next() {
                current = current.next;
                return current.data;
            }
        };
    }

    //重写ToString方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<T> current = this.head;
        while (current != null) {
            sb.append(current.data);
            current = current.next;
            if (current != null) {
                sb.append(" -> ");
            }
        }
        return sb.toString();
    }

    //对整个链表反转的方法
    public void reverse() {
        //非空判断
        if (isEmpty()) {
            return;
        }
        //调用重载的reverse方法进行反转
        reverse(head.next);
    }

    //反转链表中的某个节点的方法,并把反转后的节点返回
    private Node<T> reverse(Node<T> current) {
        if (current.next == null) {
            head.next = current;
            return current;
        } else {
            reverse(current.next).next = current;
            //递归出来后的代码，最后一个节点的next指针是null
            current.next = null;
        }
        return current;
    }

    //使用快慢指针寻找链表中间值的方法
    public T getMiddle() {
        //如果链表为空就直接返回空
        if (isEmpty()) {
            return null;
        }
        //如果链表非空
        //定义两个指针
        Node<T> fast = this.head.next;
        Node<T> slow = this.head.next;
        //使用两个指针遍历链表，当快指针没有下一个节点，此时慢指针的位置就是中间值节点
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.data;
    }
}
